package com.future;

import java.util.Arrays;

/**
 * Description:
 *
 * @author weiruibai.vendor
 * Date: 2021/9/18 10:12
 */
public class Solution_minMoves_453 {

    public static void main(String[] args) {
        Solution_minMoves_453 solution02 = new Solution_minMoves_453();
        int[] nums = {1,5,10,20};
        long s = System.currentTimeMillis();
        System.out.println(solution02.minMoves(nums));
        System.out.println(System.currentTimeMillis()-s);
        int[] nums2 = {1,5,10,20};
        long s2 = System.currentTimeMillis();
        System.out.println("正确的："+solution02.minMoves_v1(nums2));
        System.out.println(System.currentTimeMillis()-s2);
    }


    /**
     * 给定一个长度为 n 的 非空 整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数
     * <p>
     * 暴力解法
     * [1,5,10,20]
     * [2,6,11,20]
     * [3,7,12,20]
     * [4,8,13,20]
     * [5,9,14,20]
     * [6,10,15,20]
     * [7,11,16,20]
     * [8,12,17,20]
     * [9,13,18,20]
     * [10,14,19,20]
     * [11,15,20,20]  minMoves_453
     * [12,16,20,21]
     * [13,17,21,21]
     * [14,18,21,22]
     * [15,19,22,22]
     * [16,20,22,23]
     * [17,21,23,23]
     * [18,22,23,24]
     * [19,23,24,24]
     * [20,24,24,25]
     * [21,25,25,25]
     * [22,25,26,26]
     * [23,26,26,27]
     * [24,27,27,27]
     * [25,27,28,28]
     * [26,28,28,29]
     * [27,29,29,29]
     * [28,29,30,30]
     * [29,30,30,31]
     * [30,31,31,31]
     * [31,31,32,32]
     * [32,32,32,33]
     * [33,33,33,33]
     *
     * @return
     */
    public int minMoves_v1(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int timeCount = 0;
        int length = nums.length;
        Arrays.sort(nums);
        while (nums[0] != nums[length - 1]) {
            for (int i = 0; i < length - 1; i++) {
                nums[i]++;
            }
            timeCount++;
            Arrays.sort(nums);
        }
        return timeCount;
    }

    public int minMoves_v2(int[] nums) {
        int min = 0, max = nums.length - 1, count = 0;
        while (true) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[max] < nums[i]) {
                    max = i;
                }
                if (nums[min] > nums[i]) {
                    min = i;
                }
            }
            if (nums[max] == nums[min]) {
                break;
            }
            for (int i = 0; i < nums.length; i++) {
                if (i != max) {
                    nums[i]++;
                }
            }
            count++;
        }
        return count;
    }

    public int minMoves_v3(int[] nums) {
        int min = 0, max = nums.length - 1, count = 0;
        while (true) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[max] < nums[i]) {
                    max = i;
                }
                if (nums[min] > nums[i]) {
                    min = i;
                }
            }
            int diff = nums[max] - nums[min];
            if (diff == 0) {
                break;
            }
            count += diff;
            for (int i = 0; i < nums.length; i++) {
                if (i != max) {
                    nums[i] = nums[i] + diff;
                }
            }
        }
        return count;
    }

    public int minMoves_4(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            count += nums[i] - nums[0];
        }
        return count;
    }

    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = (moves + nums[i]) - nums[i - 1];
            nums[i] += moves;
            moves += diff;
        }
        return moves;
    }
}
